使用 Java 21 语言特性解决倒计时问题

Sundar Athijegannathan 于 2023 年 11 月 3 日

在 20 世纪 80 年代，游戏节目倒计时是最受欢迎的英国电视节目之一。本文旨在使用 Java 21 的语言结构来解决其数字游戏挑战。

倒计时问题

倒计时游戏节目的一项挑战是找到一种方法，使用其他数字和基本数学运算符来创建一个数字。

您将获得一个自然数列表和一个目标自然数。在本假设中，我们假设自然数集不包括 0。
您可以使用加、减、乘和除运算符。
您应该组合给定的数字和运算符，以编写一个计算结果为给定目标数字的表达式。
列表中的数字最多只能使用一次。
所有中间表达式都应计算结果为自然数。
并非所有目标数字都可以使用倒计时挑战条件表示。

例如，假设 [1, 3, 5, 7, 10, 25, 50] 是给定的自然数列表。要达成的目标数字是 765。一个可能的解决方案是 (25 - 10)*(50 + 1)。如果我们将目标数字更改为 831，则问题将没有解决方案。由于手动计算所有解决方案将花费我们时间，让我们创建一个简单的 Java 程序，该程序可以找到给定数字列表和目标数字的所有表达式。

一个用 Haskell 编程语言编写的简单而优雅的倒计时问题解决方案，在 youtube 视频中由 Prof Graham Hutton 展示。但是，在接下来的部分中，我们将把 Haskell 解决方案移植到 Java 21 语言结构中。

注意

了解 Haskell 对于理解 Java 移植不是必需的。如果您确实了解 Haskell，Java 解决方案包含有关相应 Haskell 表达式的注释。

Java 实现

我们可以从将支持的操作（加、减、乘和除）表示为枚举开始

// data Op = Add | Sub | Mul | Div
   enum Op {
       Add, Sub, Mul, Div;

       // instance show Op
       @Override
       public String toString() {
          return switch (this) {
             case Add -> "+";
             case Sub -> "-";
             case Mul -> "*";
             case Div -> "/";
          };
       }
   }
}

接下来，我们需要定义一个表达式，它可以是数字，也可以是两个子表达式与运算符组合在一起。在 Java 中，我们可以将表达式表示为一个密封接口，并将它的组件表示为记录子类型。

Haskel	Java
data Expr = Val Int \| App Op Expr Expr	sealed interface Expr {} record Val(int v) implements Expr {} record App(Op op, Expr l, Expr r) implements Expr {}

在 Val 和 App 记录子类型中允许某些常见操作，因此 Expr 密封接口定义了 brak 和 toStr 函数的行为。这些方法允许我们构造字符串并在数学项周围正确放置括号。

  // data Expr = Val Int | App Op Expr Expr
   sealed interface Expr {
      // brak helper for instance Show Expr
      static String brak(Expr expr) {
         return switch (expr) {
            // brak (Val n) = show n
            case Val(var n) -> Integer.toString(n);

            // brak e       = "(" ++ show e ++ ")"
            default -> "(" + toStr(expr) + ")";
         };
      }

      // instance Show Expr
      static String toStr(Expr expr) {
         return switch (expr) {
            // show (Val n)     = show n
            case Val(var n) -> Integer.toString(n);

            // show (App o l r) = brak l ++ show o ++ brak r
            //          where
            //             brak (Val n) = show n
            //             brak e       = "(" ++ show e ++ ")"
            case App(var op, var l, var r) -> brak(l) + op + brak(r);
         };
      }
   }

每个实现 Expr 接口的记录都在其 toString() 实现中调用 toStr 方法。

    record Val(int v) implements Expr {
      // instance Show Expr
      @Override
      public String toString() {
         return Expr.toStr(this);
      }
   }

   record App(Op op, Expr l, Expr r) implements Expr {
      // instance Show Expr
      @Override
      public String toString() {
         return Expr.toStr(this);
      }
   }

最后，我们可以将有效表达式及其值表示为 Java 记录。

// type Result = (Expr,Int)
record Result(Expr expr, int value) {
	@Override
	public String toString() {
		return expr.toString() + " = " + value;
	}
}

Haskell 实现定义了一些实用函数

检查表达式是否有效，以及
应用表达式并获取其结果。

我们可以编写一个 switch 表达式来检查表达式是否有效

   // valid' :: Op -> Int -> Int -> Bool
   static boolean isValid(Op op, int x, int y) {
      return switch (op) {
         case Add -> x <= y;
         case Sub -> x > y;
         case Mul -> x != 1 && y != 1 && x <= y;
         case Div -> y != 1 && x % y == 0;
      };
   }

为了应用表达式并获取其结果，我们将使用 switch 的模式匹配和记录模式

 // apply :: Op -> Int -> Int -> Int
   static int apply(Op op, int x, int y) {
      return switch (op) {
         case Add -> x + y;
         case Sub -> x - y;
         case Mul -> x * y;
         case Div -> x / y;
      };
   }

最后，我们需要将所有可能解决方案的生成和评估结合起来。在 Haskell 中，以下代码片段实现了这一点

   eval (Val n)     = [n | n > 0]
   eval (App o l r) = [apply o x y | x <- eval l,
                                  y <- eval r,
                                  valid o x y]

在 Java 中，我们可以再次使用 switch 的模式匹配和记录模式

   // Using OptionalInt instead of List<Integer>
   static OptionalInt eval(Expr expr) {
      return switch (expr) {
         // eval (Val n)     = [n | n > 0]
         case Val(var n) -> n > 0 ? OptionalInt.of(n) : OptionalInt.empty();


         // eval (App o l r) = [apply o x y | x <- eval l,
         //                                   y <- eval r,
         //                                   valid o x y]
         case App(var op, var l, var r) -> {
            var x = eval(l);
            var y = eval(r);
            yield (x.isPresent() && y.isPresent() &&
                   isValid(op, x.getAsInt(), y.getAsInt())) ?
               OptionalInt.of(apply(op, x.getAsInt(), y.getAsInt())) :
               OptionalInt.empty();
         }
      };
   }

运行 Java 程序而不进行编译

您可以在 samples 存储库中找到 CountDownProblem.java 的完整示例。由于该示例需要 JDK 21，因此您可以使用源代码启动器支持在不进行编译的情况下运行它。

  java CountDownProblem.java 1,3,7,10,25,50 765

总之，Java 是一种表达能力强的语言，使用其最新的语言结构帮助我们以自然的方式表示倒计时问题的數據和操作。